import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 74646
 * Date: 2022-03-10
 * Time: 16:31
 */
public class TreeHeap {
    public int[] elem;
    public int usedSize;
    public TreeHeap(){
        this.elem = new int[10];
    }

    /**
     * 交换结点的值
     * @param array 目标数组
     * @param index1 待交换结点的下标
     * @param index2 待交换结点的下标
     */
    public void swap(int[] array,int index1,int index2){
        int tmp = array[index1];
        array[index1] = array[index2];
        array[index2] = tmp;
    }

    /**
     * 向下调整
     * @param parent 每棵树的根节点
     * @param len 每棵树调整的结束位置
     */
    public void shiftDown(int parent,int len){
        int child = 2*parent+1;
        while (child<len){
            if(child+1<len && this.elem[child]<this.elem[child+1]){
                child++;
            }
            if(this.elem[child]>this.elem[parent]){
                swap(elem,child,parent);
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
//        while (child<len){
            //小根堆
//            if(child+1<len && this.elem[child]>this.elem[child+1]){
//                child++;
//            }
//            if(this.elem[child]<this.elem[parent]){
//                int tmp =this.elem[child];
//                this.elem[child] = this.elem[parent];
//                this.elem[parent] = tmp;
//                parent = child;
//                child = 2*parent+1;
//            }else {
//                break;
//            }
        }
    }

    /**
     * 创建大根堆
     * @param array 结点的值
     */
    public void createTreeHeap(int[] array){
        //拷贝数据
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
        //从最后一棵子树开始调整
        for (int parent = (usedSize-1-1)/2; parent >=0  ; parent--) {
            shiftDown(parent,usedSize);
        }
        //从根节点开始调整
//        for (int parent = 0; parent <= (usedSize-1-1)/2 ; parent++) {
//            shiftDown(parent,usedSize);
//        }
    }

    /**
     * 向上调整
     * @param child 待调整结点的下标
     */
    public void shiftUp(int child){
        int parent = (child-1)/2;
        while (child>0){
            if(this.elem[child]>this.elem[parent]){
                swap(elem,child,parent);
                child = parent;
                parent = (child-1)/2;
            }else{
                break;
            }
        }
    }
    /**
     * 优先级队列 入队操作
     * @param val 待入队的元素
     */
    public void offer(int val){
        //如果满了就进行扩容
        if(isFull()){
            this.elem = Arrays.copyOf(elem,elem.length*2);
        }
        //在最后位置插入元素
        this.elem[usedSize++] = val;
        //传入数组最后一个元素
        shiftUp(usedSize-1);
    }

    /**
     * 出队操作
     * @return 返回出队列结点的值
     */
    public int poll(){
        //如果为空就抛出异常
        if(isEmpty()){
            throw new RuntimeException("优先级队列为空！");
        }
        swap(elem,0,usedSize-1);
        int ret = this.elem[usedSize-1]; //保存交换后的堆尾元素
        usedSize--; //交换后删除
        shiftDown(0,usedSize);
        return ret;
    }

    /**
     * 获取优先级队列的队头元素
     * @return 返回队头元素
     */
    public int peek(){
        if(isEmpty()){
            throw new RuntimeException("优先级队列为空！");
        }
        return this.elem[0];
    }

    /**
     * 判断队列是否为空
     * @return 如果为空就返回true，否则返回false
     */
    public boolean isEmpty(){
        return usedSize == 0;
    }

    /**
     * 判断队列是否满了
     * @return 如果满了就返回true，否则返回去false
     */
    public boolean isFull(){
        return this.usedSize == this.elem.length;
    }

    public int lastStoneWeight(int[] stones) {
        Queue<Integer> queue = new LinkedList<>();
        int index = stones.length;
        for(int parent = ((index-1)-1)/2;parent>=0;parent--){
            int child = parent*2+1;
            while(child<index){
                if(child+1<index &&stones[child]<stones[child+1]){
                    child++;
                }
                if(stones[child]>stones[parent]){
                    int tmp = stones[child];
                    stones[child] = stones[parent];
                    stones[parent] = tmp;
                    parent = child;
                    child = parent*2+1;
                }else{
                    break;
                }
            }
        }
        for(int s:stones){
            queue.offer(s);
        }
        while(queue.size()>1){
            int top1 = queue.poll();
            int top2 = queue.poll();
            if(top1!=top2){
                queue.offer(top1-top2);
            }
        }

        if(queue.isEmpty()){
            return 0;
        }
        return queue.poll();
    }

    /**
     * 堆排序（升序）
     */
    public void heapSort(){
        int end = this.usedSize-1;
        while(end>0){
           swap(this.elem,0,end);
            shiftDown(0,end);
            end--;
        }
    }
}


